package com.chapter8;

import com.chapter10.Tnode;

public class LinkedListOperator {

	public LinkedList mergeSortedList(LinkedList l1, LinkedList l2){
		Node cur1=l1.head;
		Node cur2=l2.head;
		Node temp1=cur1.next;
		Node temp2=cur2.next;
		LinkedList list = (cur1.value<cur2.value)?l1:l2;
		
		while(true){
			while(cur1.next!=null && cur1.next.value<cur2.value)
			{
				cur1=cur1.next;
				temp1=temp1.next;
			}
			while(cur2.next!=null && cur2.next.value<cur1.value)
			{
				cur2=cur2.next;
				temp2=temp2.next;
			}
			if(cur1.value<cur2.value)
			{
				cur1.next=cur2;
				cur1=temp1;
				if(cur1==null)
					break;
				temp1=cur1.next;
			}
			else{
				cur2.next=cur1;
				cur2=temp2;
				if(cur2==null)
					break;
				temp2=cur2.next;
			}
		}
		
		return list;
	}
	
	public Node reverseSublist(LinkedList list, int l, int r){
		Node previous=null;
		Node cur=list.head;
		for(int i=0;i<l-1;i++){
			previous=cur;
			cur=cur.next;
		}
		
		Node n=cur.next;
		Node t=n.next;
		
		for(int i=0;i<r-l;i++){
			n.next=cur;
			if(t==null || i==r-l-1)
				break;
			cur=n;
			n=t;
			t=t.next;
		}
		if(l==1){
			list.head.next=t;
			list.head=n;
			return list.head;
		}
		previous.next.next=t;
		previous.next=n;
		return n;
		
	}
	
	public void reverseSublists(LinkedList list, int k){
		//find size of list
		Node cur=list.head;
		int size=0;
		while(cur!=null){
			cur=cur.next;
			size++;
		}
		int numLoop=size/k;
		for(int i=0;i<numLoop;i++){
			int l=1+k*(i);
			int r=l-1+k;
			reverseSublist(list,l,r);
		}
	}
	
	public Node checkCycle(LinkedList list){
		Node runner1=list.head;
		Node runner2=list.head;
		
		while(runner2!=null || runner1!=runner2){
			runner1=runner1.next;
			if(runner2.next==null)
				return null;
			runner2=runner2.next.next;
		}
		if(runner2==null)
			return null;
		runner1=list.head;
		while(runner1!=runner2){
			runner1=runner1.next;
			runner2=runner2.next;
		}
		return runner1;
	}
	
	public void removeDulpicates(LinkedList list){
		Node cur=list.head;
		if(cur==null)
			return;
		while(cur!=null && cur.next!=null){
			if(cur.value==cur.next.value){
				Node temp=cur.next;
				cur.next=temp.next;
				temp.next=null;
			}
			else
				cur=cur.next;
		}
		return;
	}
	
	public void cyclicShift(LinkedList list,int K){
		Node cur2=list.head;
		for(int i=0;i<K;i++)
			cur2=cur2.next;
		Node cur1=list.head;
		while(cur2.next!=null){
			cur2=cur2.next;
			cur1=cur1.next;
		}
		cur2.next=list.head;
		Node temp=cur1.next;
		cur1.next=null;
		list.head=temp;
	}
	
	public void evenOddMerge(LinkedList list){
		if(list.head==null)
			return;
		Node evenhead=list.head;
		Node oddhead=list.head.next;
		Node even=evenhead;
		Node odd=oddhead;
		
		while(even!=null && odd!=null && odd.next!=null){
			even.next=odd.next;
			even=even.next;
			odd.next=even.next;
			odd=odd.next;
		}
		
		even.next=oddhead;
		return;
	}
	
	public void interLeave(LinkedList list){
		Node cur=list.head;
		int size=0;
		while(cur!=null){
			cur=cur.next;
			size++;
		}
		int left=size/2+2;
		if(size%2==0)left--;
		Node mid=reverseSublist(list,left,size);
		
		Node cur1=list.head;
		Node cur2=mid;
		Node temp1=cur1.next;
		Node temp2=cur2.next;
		
		while(temp1!=null && temp2!=null){
			cur1.next=cur2;
			cur2.next=temp1;
			cur1=temp1;
			cur2=temp2;
			temp1=temp1.next;
			temp2=temp2.next;
		}
		cur1.next=cur2;
		if(size%2==0){
			cur2.next=null;
			return;
		}
		cur2.next=temp1;
		temp1.next=null;
		return;
	}
	
	public boolean checkPalindrome(LinkedList list){
		Node cur=list.head;
		int size=0;
		while(cur!=null){
			cur=cur.next;
			size++;
		}
		int left=size/2+2;
		if(size%2==0)left--;
		Node mid=reverseSublist(list,left,size);
		
		Node cur1=list.head;
		Node cur2=mid;
		
		
		while(cur2!=null){
			if(cur1.value!=cur2.value)
				return false;
			cur1=cur1.next;
			cur2=cur2.next;
		}
		
		return true;
	}
	
	public LinkedList add(LinkedList l1, LinkedList l2){
		LinkedList l3=new LinkedList();
		l3.head=new Node(0);
		int carry=0;
		
		Node c1=l1.head;
		Node c2=l2.head;
		Node c3=l3.head;
		while(c1!=null || c2!=null){
			if(c1!=null){
				carry=carry+c1.value;
				c1=c1.next;
			}
			if(c2!=null){
				carry=carry+c2.value;
				c2=c2.next;
			}
			c3.next=new Node(carry%10);
			c3=c3.next;
			carry=carry/10;
			
		}
		if(carry==1 && c1==null && c2==null){
			c3.next=new Node(carry);
		}
		l3.head=l3.head.next;
		return l3;
	}
	
	public Node getPivot(LinkedList l1, int k){
		Node cur=l1.head;
		while(cur.next!=null)
			cur=cur.next;
		Node tail=cur;
		cur=l1.head;
		Node pre=null;
		Node t=tail;
		//make this while loop run one more time.
		while(cur!=t){
			if(cur.value>k){
				tail.next=cur;
				tail=cur;
				cur=cur.next;
				tail.next=null;
				if(pre!=null)
					pre.next=cur;
				else
					l1.head=cur;
			}
			else{
				pre=cur;
				cur=cur.next;
			}
		/*System.out.println();
		l1.traverse();*/
		}
		
		return cur;
	}
}
